package backtrack;
import java.util.*;
public class _05_40_组合总和Ⅱ {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
	int sum = 0;
	boolean use[];
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    	use = new boolean[candidates.length];
    	Arrays.sort(candidates);
    	backtracking(candidates,target,0);
    	
    	for (List<Integer> i : result) {
			for (int j : i) {
				System.out.print(j + " ");
			}
			System.out.println();
		}
    	
    	return result;
    }
    public void backtracking(int[] candidates, int target, int index) {

    	if(sum > target) {
    		return;
    	}
    	if(sum == target) {
    		result.add(new ArrayList<Integer>(item));
    		return;
    	}
    	
    	for(int i = index; i < candidates.length; i++) {
    		/* 
    		 * 如果当前i与i-1值相同，说明i-1值的组合已经包含了当前i的组合了，则continue;
    		 * 但是i-1在遍历到i的时候，也会触发相同的条件，所以需要use用于判断当前路径中，前一个i是否使用了
    		 * 如果用了，说明是i-1在遍历，如果没用，说明是从i开始遍历的，则
    		 * 这里的判断主要是在首次根节点进入i的时候，判断前面是否有相同的值遍历过，有则跳过
    		 * */
        	if(i > 0 && candidates[i - 1] == candidates[i] && use[i-1] == false) {
        		continue;
        	}
    		sum += candidates[i];
    		item.add(candidates[i]);
    		use[i] = true;
    		backtracking(candidates, target, i + 1);
    		sum -= item.get(item.size() - 1);
    		item.remove(item.size() - 1);
    		use[i] = false;
    	}
    	
    	
    }
    
    public static void main(String[] args) {
    	int[] candidates = {2,5,2,1,2};
    	int target = 5;
		new _05_40_组合总和Ⅱ().combinationSum2(candidates, target);
	}
}
